package InsertionSort;
import LinerSearch.ArrayGenerator;
import SelectionSort.SortingHelper;

public class InsertionSort {
    /**
     * 后一个与之前元素相比，如果后一个小，互换，对于有序数组
     * 插入排序复杂度会变成O（n）级别，整体来说，还是O（n²），
     * 类似整理扑克牌，对于大部分有序的，少部分无序适合插入排序
     */
    private InsertionSort(){

    }
//    public static <E extends Comparable<E>> void sort(E[] arr){
//        for (int i=0;i<arr.length;i++){
//            int j = i+1;
//            for (int k=i;k>=0&j<arr.length;k--){
//                if (arr[j].compareTo(arr[k])<0){
//                    swap(arr,k,j);
//                    j=k;
//                }
//                else break;
//            }
//        }
//
//    }

    public static <E extends Comparable<E>> void sort(E[] arr){
        for (int i=0;i<arr.length;i++){
//            for (int j=i;j-1>=0;j--){
//                if (arr[j].compareTo(arr[j-1])<0){
//                    swap(arr,j,j-1);
//                }else break;
//            }
            for (int j=i;j-1>=0&&arr[j].compareTo(arr[j-1])<0;j--){
                swap(arr,j,j-1);
            }
        }
    }

    /**
     * 创建一个变量存储arr[i],比较后不换，变换位置改为赋值操作，减少寻址损耗
     * @param arr
     * @param <E>
     */
    public static <E extends Comparable<E>> void sort2(E[] arr){
//        for (int i=0;i<arr.length;i++){
//            E tmp = arr[i];
//            int j;
//            for (j=i;j-1>=0&&tmp.compareTo(arr[j-1])<0;j--){
//                arr[j]=arr[j-1];
//            }
//            arr[j] = tmp;
//        }
        for (int i=0;i<arr.length;i++){
            E tmp = arr[i];
            int j;
            for (j=i;j-1>=0;j--){
                if (tmp.compareTo(arr[j-1])<0)
                    arr[j]=arr[j-1];
                else break;
            }
            arr[j] = tmp;
        }
    }

    public static<E extends Comparable<E>> void swap(E[] arr,int i,int j){
        E tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
//        int[] dataSize = {10000,100000};
//        for (int n : dataSize){
//            Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
//
//            SortingHelper.sortTest("InsertionSort",arr);
//            SortingHelper.sortTest("InsertionSort2",arr);
//        }
//        Integer[] test = ArrayGenerator.generateRandomArray(10,100);
        Integer[] test = {5,4,3,9,7,2,1,58};
        InsertionSort.sort2(test);
        for (int t:test){
            System.out.print(t+" ");
        }
    }
}
